package com.Offer;

/*
    面试题51：数组中的逆序对
    题目描述：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个 数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数 P
 */
public class demo51 {
    public static void main(String[] args) {
        int[] array = {7,5,6,4};
        System.out.println(InversePairs(array));
        for (int i : array) {
            System.out.print(i+" ");
        }
    }

    public static int count = 0;

    public static int InversePairs(int[] array){
        if (array == null || array.length == 0)
            return 0;
        mergeSort(array,0,array.length-1);
        return count;
    }

    public static void mergeSort(int[] data,int start,int end){
        int mid = (start+end)/2;
        if(start < end){
            mergeSort(data,start,mid);
            mergeSort(data,mid+1,end);
            merge(data,start,mid,end);
        }
    }

    public static void merge(int[] data,int start,int mid,int end){
        int[] arr = new int[end-start+1];
        int c = 0;
        int s = start;
        int index = mid+1;
        while(start <= mid && index <= end){
            if(data[start] >= data[index]){
                arr[c++] = data[index++];
                count += mid+1-start;
                count %= 1000000007;
            }else{
                arr[c++] = data[start++];
            }
        }
        while(start <= mid){
            arr[c++] = data[start++];
        }
        while(index <= end){
            arr[c++] = data[index++];
        }

        for(int d : arr){
            data[s++] = d;
        }

    }
}
